2400. Треугольники

Миша любил рисовать треугольники, но делал он это необычным способом. Сначала рисовал произвольный треугольник, потом каждую сторону делил на n равных частей и проводил через точки раздела прямые, параллельные сторонам треугольника. В результате получается несколько равных между собой треугольников. Помогите Мише найти наибольшее количество одинаковых треугольников в его финальном рисунке.

Вход. Целое число n (0 < n < 2 * 10⁹).

Выход. Выведите наибольшее количество равных между собой треугольников.

Пример входа	Пример выхода
2	4

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Рассмотрим треугольник, каждая сторона которого поделена на n равных частей. Наибольшее количество будет достигаться среди самых маленьких треугольников, равных между собой. Подсчитаем их число.

Разобьем треугольник на n горизонтальных полос, пронумеровав их сверху вниз. Последняя n-ая (нижняя) полоса содержит n треугольников вершиной вверх и n – 1 треугольников вершиной вниз. Предпоследняя (n – 1) - ая полоса содержит n – 1 треугольников вершиной вверх и n – 2 треугольников вершиной вниз. Итого получим n + (n – 1) + (n – 2) + … + 2 + 1 треугольников вершиной вверх и (n – 1) + (n – 2) + … + 2 + 1 треугольников вершиной вниз. Общее количество одинаковых треугольников равно

2 * (n + (n – 1) + (n – 2) + … + 2 + 1) – n = = n²

Пример

При n = 1, 2, 3 количество равных треугольников составит 1, 4, 9 соответственно. При n = 3 ответ равен (1 + 2 + 3) + (1 + 2) = 9.

Реализация алгоритма

Читаем значение n, вычисляем и выводим ответ.

scanf("%lld",&n);

res = n * n;

printf("%lld\n",res);

Java реализация

import java.util.*;

class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong();

long res = n * n;

System.out.println(res);

con.close();

}

}

Python реализация

n = int(input())

res = n * n

print(res)